/// @file dag.hh
/// @brief Definition of the Directed Acyclic Graph class

// *************************************************************************

// Copyright© 2010 Texas A&M University, 
//                 College Station, Texas
//                 Contact: R Crosby <rwc@cs.tamu.edu>
//
// Copyright© 2003, 2004 by BiRC -- Bioinformatics Research Center
//                 University of Aarhus, Denmark
//                 Contact: Thomas Mailund <mailund@birc.dk>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

// *************************************************************************

#ifndef DAG_HH
#define DAG_HH

#include <list>
#include <vector>
#include <map>

using namespace std;

#include "numbers.hh"

class S;
class SMap;
class RootedTree;

class DAGNode;
class DAGInner;
class DAGRoot;
class DAGLeaf;
class DAGHash;

// *****************************************************************************
/// @brief Commmon vector type

typedef vector<large_int_t> CVEC;

// *****************************************************************************
/// @brief Directed Acyclic Graph class

class DAG {

    friend class MergeIntoDAGVisitor;

    vector<DAGRoot *>                           _roots;
    list<DAGNode *>                             _nodes;

    DAGHash *                                   _hash;

    /// Used for building the dag then cleared with ClearMaps() method
    map<pair<DAGNode *, DAGNode *>, DAGInner *> _nodetable;  

    /// Used for building the dag then cleared with ClearMaps() method
    map<S *, DAGNode *>                         _leaftable;  

    void ResetVector();
    void ResetCount();

    /// When should we prune the vectors, in percent of # of trees
    static const unsigned                       _prunePct = 5;

    /// Width of the longest tree file name 
    unsigned                                    _labelWidth;

    /// List if vectors to clear after processing current root
    vector< DAGInner * >                        _clearList;

    /// Controlling class for the set of colors
    SMap &                                      _smap;

    /// @brief Outside loop iterator across the source roots
    unsigned                                    _sourceIdx;

    /// @brief Inside loop iterator from the tree after the source to the end
    unsigned                                    _targetIdx;

    /// \brief Indicator that not all trees contain the same set of taxa
    bool                                        _dissimilar;

public:

    DAG  (SMap & map)
	: _hash(NULL), _labelWidth(0), _smap(map), _dissimilar(false)
	{}

    ~DAG ();

    /// @brief Add a tree to the DAG
    void               merge         ( RootedTree &   rt,
				       const char *   fn,
				       const unsigned ln );

    /// @brief DAG/DAG algorithm entry point
    void               count         ();
 
    /// @brief DAG/DAG algorithm count quartets compatable with current coloring
    void               nodecount     ( CVEC &  results );

    vector<DAGRoot *>& Roots         ()                 { return _roots; }
    list<DAGNode *>&   Nodes         ()                 { return _nodes; }

    const char *       Fname         (const unsigned i);
    const unsigned     LineNo        (const unsigned i);
    const unsigned     LabelWidth    ()                 { return _labelWidth; }

    DAGHash * const    Hash()        { return _hash; }

    void               MakeHashTable ( const unsigned mapSize );
    void               ClearMaps     ();

    void               print         ( ostream &os ) const;

    vector<DAGInner*>& ClearList     () { return _clearList; }

    // Return the distribution information on vector sizes
    vector<unsigned>   VSizeDist     ();

    // Return memory allocation statistics on the DAG
    unsigned long long NodeMemory    ();
    void               VectorUsage   ( unsigned long long & maxAlloc,
				       unsigned long long & maxCap,
				       unsigned long long & maxVec );

    // @brief Return the vector associated with the index...
    CVEC &             operator[]    ( unsigned i );
    
    /// @brief Return a reference to the 'S' mapping instance
    SMap &             Smap          ()                 { return _smap; }

    /// @brief Return the source tree index
    unsigned           SourceIdx     ()                 { return _sourceIdx; }
    /// @brief Return the target tree index
    unsigned           TargetIdx     ()                 { return _targetIdx; }

    /// @ brief Return the number of taxa in the specified tree
    unsigned           Taxa          (const unsigned tree);

    /// \brief Get method for the dissimilar flag
    const bool         Dissimilar    ()                 { return _dissimilar; }
    /// \brief Set methods for the disimilar flag
    void               Dissimilar    ( bool d )         { _dissimilar = d; }   

};

// *****************************************************************************
/// @brief Operator to print the DAG

inline ostream & operator<<(ostream &os, DAG &dag)
{ 
    dag.print(os); 
    return os; 
}

// *****************************************************************************
/// @brief A series of counters and methods in support of 
///        tracing the algorithm

namespace DagInfo {

    // Counters used during debugging and testing
    extern unsigned long long innerCountCalled;
    extern unsigned long long innerCountComputed;
    extern unsigned long long innerNodeCountCalled;
    extern unsigned long long innerNodeCountComputed;
    extern unsigned long long targetTraversals;
    extern unsigned long long maxVectors;
    extern unsigned long long maxVectorMemory;
    extern unsigned long long maxVectorCapacity;
    extern unsigned long long nodeMemory; 
    extern unsigned long long innerNodes;
    extern unsigned long long rootNodes;
    extern unsigned long long leafNodes;

}

#endif // DAG_HH
